package offer.algorithm;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/27 11:06
 */
public class MaxSum31 {
    public static int arrayMaxSum(int[] array) {
        if (array == null)
            return 0;
        int currentSum = array[ 0 ], maxSum = array[ 0 ];
        int start = 0, end = 0;
        for (int i = 1; i < array.length; i++) {
            if (currentSum < 0 && array[ i ] > 0) {
                start = i;
                currentSum = array[ i ];
                maxSum = array[ i ];
            }
            else if (array[i] < 0 && currentSum + array[ i ] > 0 ) {
                currentSum += array[ i ];
            }
            else if (currentSum > 0 && array[ i ] > 0) {
                currentSum += array[ i ];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                    end = i;
                }
            }
        }
        System.out.println("start: "+ start+"    "+"end: "+end);
        return maxSum;
    }


}
